package stack_queue.leetcode;

import java.util.Stack;

/**
 * 括号匹配问题
 * https://leetcode-cn.com/problems/valid-parentheses/
 */
public class Num20 {
    public boolean isValid(String s) {
        // 遍历字符串,在遍历过程中，将左括号全部入栈
        // 碰到右括号就弹出栈顶元素查看是否匹配
        // 1.将字符串转为字符数组 String -> char[]
        Stack<Character> stack = new Stack<>();
        char[] ret = s.toCharArray();
        for (int i = 0; i < ret.length; i++) {
            char c = ret[i];
            // 判断c是否是左括号
            if (c == '{' || c == '[' || c == '(') {
                stack.push(c);
            }else {
                // "]"
                if (stack.isEmpty()) {
                    return false;
                }
                // 此时c是个右括号
                char tmp = stack.pop();
                if (c == '}' && tmp != '{') {
                    return false;
                }
                if (c == ']' && tmp != '[') {
                    return false;
                }
                if (c == ')' && tmp != '(') {
                    return false;
                }
            }
        }
        return stack.isEmpty();
    }
}
